#include <bits/stdc++.h>
#define MAXN 3000500
#define ll long long
using namespace std;

inline long long get_num() {
	int k = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c) ; c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}

int want[MAXN];
int n, k;

int main() {
	freopen("empty.in", "r", stdin);
	freopen("empty.out", "w", stdout);
	n = get_num();
	k = get_num();
	
	
	for(ll i = 1; i <= k; i++) {
		int x = get_num();
		int y = get_num();
		int a = get_num();
		int b = get_num();
		for(int j = 1; j <= y; j++) {
			int tmp = (((a % n) * (j % n)) % n + b % n) % n;
			want[tmp] += x;
		}
	}
	int tmp = 0;
	for(int i = 0; i < n; i++) {
		if(want[i]) {
			if(want[i] > 1) {
				tmp += want[i] - 1;
				want[i] = 1;
			}
		} else if(tmp) {
			want[i] = 1;
			tmp--;
		}
	}
	for(int i = 0; i < n; i++) {
		if(!want[i]) {
			if(tmp) {
				want[i] = 1;
				tmp--;
			}
			else {
				printf("%d", i);
				return 0;
			}
		}
	}
}

